/*********************************************************************************
    This software is created under the term GNU General Public License.
    You should have received a copy of the GNU General Public License.
    If not, write to the Free Software Foundation, 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.

heap:
    a pool of memory. see the comment

author: xiangyun.kong(lo-sor@hotmail.com)
create: 2-26-2011

changes:

**********************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "heap.h"

// get _hpn off from the heap chain
void _hp_off( heap *_hp, hp_node *_hpn );
// put _hpn into the heap chain where behind the _pre and at the front of _nxt
void _hp_in( heap *_hp, hp_node *_hpn, hp_node *_pre, hp_node *_nxt );

// add a new heap of _sz bytes to the pool. if _sz is 0,
// we create a heap with default size(HEAP_BLK_MAX_SIZE)
int hp_enlarge( heap *_hp, int32 _sz )
{
    hp_node *nnd;
    int iused = 0;

    if( _sz == 0 )
        _sz = HEAP_BLK_MAX_SIZE;

    // find the place for holding the new heap's point
    while( iused < _hp->iblk && _hp->blk[iused] != NULL )
        ++iused;

    // if all the places are used, we enlarge the place
    if( iused == _hp->iblk )
    {
        _hp->blk = (void**)realloc( _hp->blk, sizeof(void*) * _hp->iblk * 2 );
        assert( _hp->blk != NULL );
        memset( _hp->blk + sizeof(void*) * _hp->iblk, 0, sizeof(void*) * _hp->iblk );
        _hp->iblk *= 2;
    }

    _hp->blk[iused] = malloc( _sz );
    assert( _hp->blk[iused] != NULL );

    // make the new memory to a heap(make head and init it)
    nnd = (hp_node*) _hp->blk[iused];
    nnd->size = _sz;
    nnd->free = 1;
    nnd->nxt = _hp->begin;
    nnd->pre = NULL;
    nnd->dnxt = NULL;
    nnd->dpre = NULL;

    // add the new heap to the pool
    _hp->begin->pre = nnd;
    _hp->begin = nnd;

    return 0;
}

heap* hp_create( )
{
    heap *_hp;
    _hp = (heap*)malloc( sizeof(heap) );
    assert( _hp != NULL );

    _hp->iblk = 16;
    _hp->blk = (void**)malloc( sizeof(void*) * _hp->iblk );
    assert( _hp->blk != NULL );
    memset( _hp->blk, 0, sizeof(void*) * _hp->iblk );

    _hp->blk[0] = malloc( HEAP_BLK_MAX_SIZE );
    assert( _hp->blk[0] != NULL );

    _hp->begin = _hp->end = (hp_node*) _hp->blk[0];
    _hp->begin->size = HEAP_BLK_MAX_SIZE;
    _hp->begin->free = 1;
    _hp->begin->nxt = NULL;
    _hp->begin->pre = NULL;
    _hp->begin->dnxt = NULL;
    _hp->begin->dpre = NULL;

    return _hp;
}

void hp_release( heap *_hp )
{
    int i = 0;
    while( i < _hp->iblk && _hp->blk[i] != NULL )
    {
        free( _hp->blk[i] );
        _hp->blk[i] = NULL;
    }
    free( _hp->blk );
}

void* hp_alloc( heap *_hp, uint32 _sz )
{
    hp_node *hpn;

    // try to find the heap who can hold _sz bytes
    hpn = _hp->begin;
    while( hpn )
    {
        if( hpn->size < HEAP_LARGE_BLK && 
            _sz + sizeof(hp_node) >= HEAP_LARGE_BLK )
        {
            hpn = NULL;
            break;
        }
        if( hpn->size == _sz + sizeof(hp_node) ||
            hpn->size > _sz + sizeof(hp_node) * 2 )
            break;
        hpn = hpn->nxt;
    }

    // if no such heap( with size >= _sz ), we create
    // a large enough heap for it.
    if( hpn == NULL )
    {
        hp_enlarge( _hp, 
            _sz + sizeof(hp_node) > HEAP_BLK_MAX_SIZE ? 
            _sz + sizeof(hp_node) : 0 );
        hpn = _hp->begin;
    }

    // if the heap just matches the size, we return the memory
    // of the heap
    if( hpn->size == _sz + sizeof(hp_node) )
    {
        hpn->free = 0;
        _hp_off( _hp, hpn );
    }
    else    // else, we need seperate the heap into two smaller ones. and
            // then return one of them, who just matches the size
    {
        // hpx is the unmatched one, we should add it to the pool for later use
        hp_node *hpx;
        hpx = (hp_node *)( (char*)hpn + _sz + sizeof(hp_node) );
        hpx->dpre = hpn;
        hpx->dnxt = hpn->dnxt;
        hpn->dnxt = hpx;

        hpx->free = 1;
        hpx->size = hpn->size - _sz - sizeof(hp_node);
        _hp_in( _hp, hpx, hpn, hpn->nxt );

        // now hpn matches the size, we return it
        hpn->free = 0;
        hpn->size = _sz + sizeof(hp_node);
        _hp_off( _hp, hpn );
    }
    return (char*)hpn + sizeof(hp_node);
}

void hp_free( heap *_hp, void *_data )
{
    hp_node *hpx;
    hpx = (hp_node*)( (char*)_data - sizeof(hp_node) );

    // if the two brother of heap are all freed, we combine them
    if( hpx->dpre && hpx->dpre->free )
    {
        hpx->dpre->size += hpx->size;
        hpx->dpre->dnxt = hpx->dnxt;
        if( hpx->dnxt )     
            hpx->dnxt->dpre = hpx->dpre;
        hpx = hpx->dpre;
        _hp_off( _hp, hpx );
    }

    // if the two brother of heap are all freed, we combine them
    if( hpx->dnxt && hpx->dnxt->free )
    {
        _hp_off( _hp, hpx->dnxt );
        hpx->size += hpx->dnxt->size;
        if( hpx->dnxt->dnxt )   
            hpx->dnxt->dnxt->dpre = hpx;
        hpx->dnxt = hpx->dnxt->dnxt;
    }
    // now,hpx is a large heap(if it can combine)
    hpx->free = 1;
    // if it is large enough, we put it at the head of the pool(for fast
    // match when alloc memory)
    if( hpx->size >= HEAP_LARGE_BLK )
        _hp_in( _hp, hpx, NULL, _hp->begin );
    else // else, we put it at the end of the pool
        _hp_in( _hp, hpx, _hp->end, NULL );
}

void _hp_off( heap *_hp, hp_node *_hpn )
{
    if( _hpn->pre )
        _hpn->pre->nxt = _hpn->nxt;
    if( _hpn->nxt )
        _hpn->nxt->pre = _hpn->pre;
    if( _hp->begin == _hpn )
        _hp->begin = _hpn->nxt;
    if( _hp->end == _hpn )
        _hp->end = _hpn->pre;
}

void _hp_in( heap *_hp, hp_node *_hpn, hp_node *_pre, hp_node *_nxt )
{
    _hpn->pre = _pre;
    _hpn->nxt = _nxt;
    if( _pre )
        _pre->nxt = _hpn;
    else
        _hp->begin = _hpn;
    if( _nxt )
        _nxt->pre = _hpn;
    else
        _hp->end = _hpn;
}

uint32 hp_size( void *_data )
{
    hp_node *hpx;
    hpx = (hp_node*)( (char*)_data - sizeof(hp_node) );
    return hpx->size - sizeof(hp_node);
}
